package range;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

/**
 * @author hht
 * @ClassName  RangeModule
 * @Description https://leetcode-cn.com/problems/range-module/
 * @Date 2019/12/19 10:45
 * @VERSION 1.0
 */
class RangeModule {
    TreeMap<Integer, Integer> intervals = new TreeMap<>();
    //依赖 TreeMap 默认 key 有序，方便范围查询 ,每对key-value 代表一个范围端key 为 left value为 right

    public static void main(String[] args) {
        RangeModule rangeModule = new RangeModule();
        rangeModule.addRange(1,4);
        rangeModule.addRange(8,20);
        System.out.println(rangeModule.queryRange(1,3));
        System.out.println( rangeModule.queryRange(9,13));

    }
    public void addRange(int left, int right) {
        Integer start = intervals.floorKey(left);//获取 小于等于left的 最大key
        Integer end = intervals.floorKey(right);

        //判断本次范围段是否和别的范围段交接，交接的话联合在一起 获取一个更大的范围段
        if(start != null && intervals.get(start) >= left){
            left = start;
        }
        if(end != null && intervals.get(end) > right){
            right = intervals.get(end);
        }
        intervals.put(left, right);
        intervals.subMap(left, false, right, true).clear();//清空本次范围段 完全包含在内的 无效范围段
    }
    public boolean queryRange(int left, int right) {
        Integer start = intervals.floorKey(left);
        return  start != null && intervals.get(start) >= right;
    }
    public void removeRange(int left, int right) {
        Integer start = intervals.floorKey(left);
        Integer end = intervals.floorKey(right);

        if(end != null && intervals.get(end) > right){
            intervals.put(right, intervals.get(end));
        }
        if(start != null && intervals.get(start) > left){
            intervals.put(start, left);
        }
        intervals.subMap(left, true, right, false).clear();
    }

}
